package com.itcast.demo.simple;

/**
 * 给定一个数组arr，返回子数组的最大累加和
 * 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
 * 题目保证没有全为负数的数据
 * [要求]
 * 时间复杂度为O(n)，空间复杂度为O(1)
 *
 * @author zheng.zhang
 */
public class Test10 {

    public static void main(String[] args) {
        Test10 test10 = new Test10();
        int[] arr = {1, -2, 3, 5, -2, 6, -1};
        System.out.println(test10.maxSumOfSubarray(arr));
    }

    /**
     * max sum of the subarray
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxSumOfSubarray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // TODO 抄的,待学习
        int max = Integer.MIN_VALUE;
        int curr = 0;
        for (int val : arr) {
            curr += val;
            max = Math.max(curr, max);
            curr = Math.max(curr, 0);
        }
        return max;
    }
}
